#include "MatGraph.cpp"	

void dfs(MatGraph &g, int v, bool visited[]) {
    //访问顶点v
    // 设置访问标记，输出顶点
    visited[v] = true;	
    printf("%d ", v);	
    // 遍历所有邻接点
    for (int w = 0; w < g.n; w++) {	
        //如果有边且未访问
        if (g.edges[v][w] != 0 && g.edges[v][w] < INF && !visited[w]) {	
            //递归访问邻接点w
            dfs(g, w, visited);	
        }
    }
}

void listConnectedComponents(MatGraph &g) {
    //初始化访问标志数组
    bool visited[MAXVEX] = {false};	
    //遍历所有顶点    
    for (int i = 0; i < g.n; i++) {	
        //如果未访问
        if (!visited[i]) {	
            //深度优先遍历
            printf("连通分量: ");
            dfs(g, i, visited);	
            printf("\n");
        }
    }
}

int main() {
    MatGraph g;
    int n = 8, e = 6, i;
    CreateGraph(g, n);	
    // 插入边
    // 0 7 5
    InsertEdge1(g, 0, 7, 5);	//插入边(0,7)权值为5
    // 0 1 4
    InsertEdge1(g, 0, 1, 4);	//插入边(0,1)权值为4
    // 2 0 9
    InsertEdge1(g, 2, 0, 9);	//插入边(2,0)权值为9
    // 4 1 7
    InsertEdge1(g, 4, 1, 7);	//插入边(4,1)权值为7
    // 2 4 6
    InsertEdge1(g, 2, 4, 6);	//插入边(2,4)权值为6
    // 3 5 3
    InsertEdge1(g, 3, 5, 3);	//插入边(3,5)权值为3

    printf("图G的邻接矩阵:\n");
    DispMatGraph(g);
    printf("图G的邻接表:\n");
    DispAdjGraph(g);

    listConnectedComponents(g);	//输出连通分量

    DestroyGraph(g);
}